/*
https://leetcode-cn.com/problems/sliding-window-median/solution/hua-dong-chuang-kou-zhong-wei-shu-by-lee-7ai6/
 */
import java.util.*;

public class Solution480 {
    public double[] medianSlidingWindow(int[] nums, int k) {
        DuelHeap duelHeap=new DuelHeap(k);
        for (int i=0;i<k;i++){
            duelHeap.insert(nums[i]);
        }
        double[] ans=new double[nums.length-k+1];
        ans[0]=duelHeap.getMedian();
        for (int i=k;i<nums.length;i++){
            duelHeap.insert(nums[i]);
            duelHeap.erase(nums[i-k]);
            ans[i-k+1]=duelHeap.getMedian();
        }
        return ans;
    }

    static class DuelHeap{

        PriorityQueue<Integer> small=new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> large=new PriorityQueue<>();
        Map<Integer,Integer> delay=new HashMap<>();
        int smallSize,largeSize;
        int k;

        public DuelHeap(int k) {
            this.k=k;
        }

        public void insert(int num) {
            if (smallSize==0 || num<=small.peek()){
                small.offer(num);
                smallSize++;
            }else{
                large.offer(num);
                largeSize++;
            }
            makeBalance();
        }

        private void makeBalance() {
            if (smallSize>largeSize+1){
                large.offer(small.poll());
                smallSize--;
                largeSize++;
                prune(small);
            }else if (smallSize<largeSize){
                small.offer(large.poll());
                largeSize--;
                smallSize++;
                prune(large);
            }

        }

        public double getMedian() {
            return k%2==1?small.peek():((double)small.peek()+large.peek())/2;
        }

        public void erase(int num) {
            delay.put(num,delay.getOrDefault(num,0)+1);
            if (num<=small.peek()){
                smallSize--;
                if (num==small.peek()){
                    prune(small);
                }
            }else{
                largeSize--;
                if (num==large.peek()){
                    prune(large);
                }
            }
            makeBalance();
        }

        private void prune(PriorityQueue<Integer> queue) {
            while (!queue.isEmpty()){
                int num=queue.peek();
                if (delay.getOrDefault(num,0)!=0){
                    delay.put(num,delay.get(num)-1);
                    queue.poll();
                }else{
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution480().medianSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3)));
    }
}
